package pri.hillchen.algorithm.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 获取数组中两个数之和为目标值的所有组合
 * Created by hillchen on 2017/9/26 0026.
 */
public class TwoSumToTagert {
    List<int[]> towSumToTagert(int[] nums,int target){
        List<int[]> ret = new ArrayList<int[]>();
        //先排序同时记录排序后最接近target/2的index下标
        int targetMid = target/2;

        int arrayLenth = nums.length;
        int i = 0,j=arrayLenth -1;
        boolean checkLeft = true;
        Integer tempLeft = null;
        while (i<= j){
            if(checkLeft){
                if(nums[i] > targetMid){
                    tempLeft = nums[i];
                    checkLeft = false;
                }else{
                    i ++;
                }
            }else{
                if(nums[j] < targetMid){
                    if(tempLeft != null ){
                        nums[i] = nums[j];
                        nums[j] = tempLeft;
                        tempLeft = null;
                        i++;
                        j--;
                    }
                    checkLeft = true;
                }else{
                    j --;
                }
            }
        }

        if(i == j){
            j ++;
        }
        Arrays.sort(nums,0,i );
        Arrays.sort(nums,j,arrayLenth );

        int sum;
        while(i >= 0 && j < arrayLenth){
            sum = nums[i] + nums[j];
            if(sum == target){
                ret.add(new int[]{nums[i],nums[j]});
                int temp = nums[i];
                while(--i >=0 && nums[i] == temp);
                temp =nums[j];
                while (++j < arrayLenth && nums[j] == temp);
            }else if(sum > target){
                i --;
            }else{
                j++;
            }

        }
        return ret;
    }

    public static void main(String[] args){
        int[] array = {1,2,9,3,8,7,6,4,5,5,10,0,15,-5,20,22,-12};
        List<int[]> target10 = new TwoSumToTagert().towSumToTagert(array,10);
        for(int[] sub:target10){
            System.out.println(sub[0]+","+sub[1]);
        }
    }
}
